<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/16x16.png">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Lato', 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic|Cambria', 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic|Verdana', Lato, 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"yoursite.com","root":"/","scheme":"Mist","version":"7.8.0","exturl":false,"sidebar":{"position":"right","display":"hide","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="Problem 352 Blood tests Each one of the 25 sheep in a flock must be tested for a rare virus, known to affect 2% of the sheep population. An accurate and extremely sensitive PCR test exists for blood">
<meta property="og:type" content="article">
<meta property="og:title" content="Problem 352">
<meta property="og:url" content="http://yoursite.com/352/index.html">
<meta property="og:site_name" content="Project Euler | 欧拉计划">
<meta property="og:description" content="Problem 352 Blood tests Each one of the 25 sheep in a flock must be tested for a rare virus, known to affect 2% of the sheep population. An accurate and extremely sensitive PCR test exists for blood">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2011-10-02T08:00:00.000Z">
<meta property="article:modified_time" content="2015-10-25T07:06:54.000Z">
<meta property="article:author" content="sx349">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="http://yoursite.com/352/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>Problem 352 | Project Euler | 欧拉计划</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Project Euler | 欧拉计划</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-problem">

    <a href="/problems" rel="section"><i class="fa fa-tags fa-fw"></i>题目</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/352/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.png">
      <meta itemprop="name" content="sx349">
      <meta itemprop="description" content="Project Euler | 欧拉计划 中文翻译站">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Project Euler | 欧拉计划">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          Problem 352
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">题目发布于</span>

              <time title="发布时间：2011-10-02 01:00:00" itemprop="dateCreated datePublished" datetime="2011-10-02T01:00:00-07:00">2011-10-02</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">翻译更新于</span>
                <time title="更新时间：2015-10-25 00:06:54" itemprop="dateModified" datetime="2015-10-25T00:06:54-07:00">2015-10-25</time>
              </span>

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <hr>
<h1 id="Problem-352"><a href="#Problem-352" class="headerlink" title="Problem 352"></a><a href="https://projecteuler.net/problem=352" target="_blank" rel="noopener">Problem 352</a></h1><hr>
<p><strong>Blood tests</strong></p>
<p>Each one of the 25 sheep in a flock must be tested for a rare virus, known to affect 2% of the sheep population. An accurate and extremely sensitive PCR test exists for blood samples, producing a clear positive / negative result, but it is very time-consuming and expensive.</p>
<p>Because of the high cost, the vet-in-charge suggests that instead of performing 25 separate tests, the following procedure can be used instead:</p>
<p>The sheep are split into 5 groups of 5 sheep in each group. For each group, the 5 samples are mixed together and a single test is performed. Then,</p>
<ul>
<li>If the result is negative, all the sheep in that group are deemed to be virus-free.</li>
<li>If the result is positive, 5 additional tests will be performed (a separate test for each animal) to determine the affected individual(s).</li>
</ul>
<p>Since the probability of infection for any specific animal is only 0.02, the first test (on the pooled samples) for each group will be:</p>
<ul>
<li>Negative (and no more tests needed) with probability 0.98<sup>5</sup> = 0.9039207968.</li>
<li>Positive (5 additional tests needed) with probability 1 - 0.9039207968 = 0.0960792032.</li>
</ul>
<p>Thus, the expected number of tests for each group is 1 + 0.0960792032 × 5 = 1.480396016.<br>Consequently, all 5 groups can be screened using an average of only 1.480396016 × 5 = <b>7.40198008</b> tests, which represents a huge saving of more than 70% !</p>
<p>Although the scheme we have just described seems to be very efficient, it can still be improved considerably (always assuming that the test is sufficiently sensitive and that there are no adverse effects caused by mixing different samples). E.g.:</p>
<ul>
<li>We may start by running a test on a mixture of all the 25 samples. It can be verified that in about 60.35% of the cases this test will be negative, thus no more tests will be needed. Further testing will only be required for the remaining 39.65% of the cases.</li>
<li>If we know that at least one animal in a group of 5 is infected and the first 4 individual tests come out negative, there is no need to run a test on the fifth animal (we know that it must be infected).</li>
<li>We can try a different number of groups / different number of animals in each group, adjusting those numbers at each level so that the total expected number of tests will be minimised.</li>
</ul>
<p>To simplify the very wide range of possibilities, there is one restriction we place when devising the most cost-efficient testing scheme: whenever we start with a mixed sample, all the sheep contributing to that sample must be fully screened (i.e. a verdict of infected / virus-free must be reached for all of them) before we start examining any other animals.</p>
<p>For the current example, it turns out that the most cost-efficient testing scheme (we’ll call it the <i>optimal strategy</i>) requires an average of just <b>4.155452</b> tests!</p>
<p>Using the optimal strategy, let T(s,p) represent the average number of tests needed to screen a flock of s sheep for a virus having probability p to be present in any individual.<br>Thus, rounded to six decimal places, T(25, 0.02) = 4.155452 and T(25, 0.10) = 12.702124.</p>
<p>Find ΣT(10000, p) for p=0.01, 0.02, 0.03, … 0.50.<br>Give your answer rounded to six decimal places.</p>
<hr>
<p><strong>血液检测</strong></p>
<p>一群共25只羊需要逐一检测是否感染了一种罕见的病毒，已知这种病毒在羊群中的感染率为2%。现在有一种准确而极为敏感的PCR检测，能够对血液样品给出明确的阳性或阴性的结论，但这种监测非常耗时而且昂贵。</p>
<p>出于成本考虑，兽医负责人建议，并不需要进行25次分别检测，而是采用以下的做法：</p>
<p>首先将羊群分成5组，每组有5只羊。在每一组中，将5份血液样品混合在一起进行一次检测。随后，</p>
<ul>
<li>如果结果呈阴性，这一组中所有的羊一定都没有感染病毒。</li>
<li>如果结果呈阳性，再进行5次检测（每只羊一次）以确认被感染的个体。</li>
</ul>
<p>由于每只羊感染的概率仅为0.02，每组第一次检测（对混合血液样品）的结果将会；</p>
<ul>
<li>有0.98<sup>5</sup> = 0.9039207968的概率为阴性（不需要再进行检测）。</li>
<li>有1 - 0.9039207968 = 0.0960792032的概率为阳性（需要再进行5次检测）。</li>
</ul>
<p>因此，每一组的期望检测次数为1 + 0.0960792032 × 5 = 1.480396016。<br>由此，所有5个组总共需要1.480396016 × 5 = <b>7.40198008</b>次检测，比最初的方案节省了超过70%！</p>
<p>尽管上述安排看起来非常有效，它仍然有很大的改进空间（前提是这种检测充分敏感以及混合不同的样品不会有副作用）。例如：</p>
<ul>
<li>我们可以在一开始先混合所有25份血液样品进行一次检测。可以验证，在大约60.35%的情况下，检测结果会是阴性，因此不需要再进行更多的检测。只有在剩下的39.65%的情况下需要进一步检测。</li>
<li>如果我们知道在一组5只羊中至少有一只感染了病毒，而前4只的检测结果均为阴性，那么就不需要对第五只羊进行检测（我们知道它一定被感染了）。</li>
<li>我们可以尝试其它的组数或每组的羊数，通过调整这些数目使得期望总检测数最小。</li>
</ul>
<p>为了简化这个问题非常宽泛的各种可能性，我们对于成本最低的检测安排有一个限制要求：如果我们检测了一份混合样品，必须先完全确认该样品中所有的羊（也就是对每只羊给出一个感染或未感染的结论）之后才能检测其它的羊。</p>
<p>在上述样例中，成本最低的检测安排（我们称之为<i>最优策略</i>）平均仅需要<b>4.155452</b>次检测！</p>
<p>现在有一群共s只羊和一种感染率为p的病毒，记T(s,p)为最优策略所需要的平均检测次数。<br>已知在四舍五入到六位小数时，T(25, 0.02) = 4.155452以及T(25, 0.10) = 12.702124。</p>
<p>对于p=0.01、0.02、0.03、……、0.50，求ΣT(10000, p)。<br>将你的答案四舍五入到六位小数。</p>
<hr>

    </div>

    
    
    

      <footer class="post-footer">

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/351/" rel="prev" title="Problem 351">
      <i class="fa fa-chevron-left"></i> Problem 351
    </a></div>
      <div class="post-nav-item">
    <a href="/353/" rel="next" title="Problem 353">
      Problem 353 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="gitalk-container"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#Problem-352"><span class="nav-text">Problem 352</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="sx349"
      src="/images/avatar.png">
  <p class="site-author-name" itemprop="name">Leonhard Euler(1707-1783)</p>
  <p class="site-description motion-element">Project Euler | 欧拉计划<br>中文翻译站</p>
</div>
  <div class="cc-license motion-element" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-title">
          <a href="https://projecteuler.net/" title="https:&#x2F;&#x2F;projecteuler.net" rel="noopener" target="_blank">Project Euler</a>
        </li>
        <li class="links-of-blogroll-title">
          <a href="http://jakwings.is-programmer.com/Project_Euler" title="http:&#x2F;&#x2F;jakwings.is-programmer.com&#x2F;Project_Euler" rel="noopener" target="_blank">饮水思源汉化</a>
        </li>
        <li class="links-of-blogroll-title">
          <a href="http://sx349.github.io/" title="http:&#x2F;&#x2F;sx349.github.io" rel="noopener" target="_blank">译者博客</a>
        </li>
    </ul>
  </div>

      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2001 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fas fa-calculator"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Project Euler | 欧拉计划</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://mist.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/muse.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  
      

<script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      loader: {
        source: {
          '[tex]/amsCd': '[tex]/amscd',
          '[tex]/AMScd': '[tex]/amscd'
        }
      },
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              let target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    (function () {
      var script = document.createElement('script');
      script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
      script.defer = true;
      document.head.appendChild(script);
    })();
  } else {
    MathJax.startup.document.state(0);
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.css">

<script>
NexT.utils.loadComments(document.querySelector('#gitalk-container'), () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js', () => {
    var gitalk = new Gitalk({
	  title       : document.title.substr(0,29),
      clientID    : '4ba99a8839c5e7dde683',
      clientSecret: '3984f7cad409553d6afde8dbc2c08fc425e7bbdc',
      repo        : 'pe-cn-comments',
      owner       : 'pe-cn',
      admin       : ['sx349'],
      id          : 'eb1ae1f1a5365dc0b8f92fe28982f249',
        language: '',
      distractionFreeMode: true
    });
    gitalk.render('gitalk-container');
  }, window.Gitalk);
});
</script>

</body>
</html>
